﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0109_CanConstruct : IAlgorithm
    {
        // 383. 赎金信

        // 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

        // 如果可以，返回 true ；否则返回 false 。

        // magazine 中的每个字符只能在 ransomNote 中使用一次。

        // 提示：
        //  1 <= ransomNote.length, magazine.length <= 10^5
        //  ransomNote 和 magazine 由小写英文字母组成

        public void Test()
        {
            // 算法参数定义
            string ransomNote = "", magazine = "";
            // 算法执行与打印
            Console.WriteLine(CanConstruct(ransomNote, magazine));
        }

        // 算法
        public bool CanConstruct(string ransomNote, string magazine)
        {
            if (ransomNote.Length > magazine.Length)
                return false;
            var dic = new Dictionary<char, int>();
            foreach (var item in ransomNote)
                if (dic.ContainsKey(item))
                    dic[item]++;
                else
                    dic.Add(item, 1);
            foreach (var item in magazine)
            {
                if (dic.ContainsKey(item))
                    if (dic[item] == 1)
                        dic.Remove(item);
                    else
                        dic[item]--;
                if (dic.Count == 0)
                    return true;
            }
            return false;
        }
    }
}
